/**
 * @(#) CompositorSemantico.java
 */

package br.cnpq.webflowah.inferencia;

import java.net.URI;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import br.cnpq.webflowah.beans.Conceito;
import br.cnpq.webflowah.beans.Objetivo;
import br.cnpq.webflowah.beans.Operacao;

/**
 * Compoe planos de execucao para um workflow semantico
 * 
 */
public class CompositorSemantico {

	private static final Logger log = Logger
			.getLogger(CompositorSemantico.class);
	private SeletorSemantico seletor;

	/* Elementos do workflow */

	private List<URI> entradasUsuario;

	private List<URI> precondicoesUsuario;

	private List<URI> efeitosUsuario;

	private List<URI> saidasUsuario;

	private List<Objetivo> processosUsuario;

	/* Conjuntos do compositor */

	private List<URI> entradasDesejaveis;

	private List<URI> entradasPossiveis;

	private List<URI> entradasDisponiveis;

	// private List<URI> precondicoesPossiveis;

	// private List<URI> precondicoesDisponiveis;

	private List<Operacao> operacoesPossiveis;

	private List<Operacao> operacoesUteisSePossiveis;

	private List<Operacao> operacoesUteis;

	// private List<Operacao> operacoesDescartadas;

	private List<URI> saidasDesejaveis;

	private List<URI> saidasDescartadas;

	// private List<URI> efeitosDesejaveis;

	private List<Objetivo> processosDesejaveis;

	// private List<Objetivo> processosPossiveis;

	private List<List<Operacao>> caminhosDeExecucao;

	// private List<List<Operacao>> grafoExecucao;

	public CompositorSemantico() {
		seletor = new SeletorSemantico();
	}

	/**
	 * Compoe planos de execucao a partir de uma descricao de workflow
	 * 
	 */
	public List<List<Operacao>> doCompor(List<URI> entradas, List<URI> saidas,
			List<Objetivo> objetivos, List<URI> descartes) throws Exception {
		long inicial = System.currentTimeMillis();
		inicializar(entradas, saidas, objetivos, descartes);
		log.debug("Tempo para inicializar: "
				+ (System.currentTimeMillis() - inicial));

		inicial = System.currentTimeMillis();
		selecionarOperacoesUteis();
		log.debug("Tempo para selecionar operacoes uteis: "
				+ (System.currentTimeMillis() - inicial));

		inicial = System.currentTimeMillis();
		gerarCaminhosDeExecucao();
		log.debug("Tempo para gerarCaminhos: "
				+ (System.currentTimeMillis() - inicial));
		// criarGrafoExecucao();

		// otimizarGrafoExecucao();

		if (caminhosDeExecucao.size() == 0) {
			throw new Exception("Não foi possível encontrar uma composição");
		}

		return caminhosDeExecucao;
	}

	/**
	 * Inicializa conjuntos
	 * 
	 */
	private void inicializar(List<URI> entradas, List<URI> saidas,
			List<Objetivo> objetivos, List<URI> descartes) {

		/* workflow */
		entradasUsuario = new ArrayList<URI>();
		entradasUsuario.addAll(entradas);

		saidasUsuario = new ArrayList<URI>();
		saidasUsuario.addAll(saidas);

		processosUsuario = new ArrayList<Objetivo>();
		processosUsuario.addAll(objetivos);

		efeitosUsuario = new ArrayList<URI>();

		precondicoesUsuario = new ArrayList<URI>();

		entradasDesejaveis = new ArrayList<URI>();

		for (int i = 0; i < objetivos.size(); i++) {
			Objetivo objetivo = objetivos.get(i);

			List entradas1 = objetivo.getEntradas();
			for (int j = 0; entradas1 != null && j < entradas1.size(); j++) {
				Conceito entrada = (Conceito) entradas1.get(j);
				URI uri = URI.create(entrada.getURI());
				if (entradasDesejaveis.indexOf(uri) < 0)
					entradasDesejaveis.add(uri);
			}

			List efeitos = objetivo.getEfeitos();
			for (int j = 0; efeitos != null && j < efeitos.size(); j++) {
				Conceito efeito = (Conceito) efeitos.get(j);
				URI uri = URI.create(efeito.getURI());
				if (efeitosUsuario.indexOf(uri) < 0)
					efeitosUsuario.add(uri);
			}

			List precondicoes = objetivo.getPreCondicoes();
			for (int j = 0; precondicoes != null && j < precondicoes.size(); j++) {
				Conceito precondicao = (Conceito) precondicoes.get(j);
				URI uri = URI.create(precondicao.getURI());
				if (precondicoesUsuario.indexOf(uri) < 0)
					precondicoesUsuario.add(uri);
			}
		}

		/*
		 * AQUIIII System.out.println("Entradas do usu�rio = " +
		 * entradasUsuario); System.out.println("Saidas do usu�rio = " +
		 * saidasUsuario); System.out.println("Precondicoes do usu�rio = " +
		 * precondicoesUsuario); System.out.println("Efeitos do usu�rio = " +
		 * efeitosUsuario);
		 */

		/* compositor */
		entradasPossiveis = new ArrayList<URI>();
		entradasPossiveis.addAll(entradasDesejaveis);

		entradasDisponiveis = new ArrayList<URI>();
		entradasDisponiveis.addAll(entradasDesejaveis);

		// precondicoesPossiveis = new ArrayList<URI>();
		// precondicoesPossiveis.addAll(precondicoes);

		// precondicoesDisponiveis = new ArrayList<URI>();
		// precondicoesDisponiveis.addAll(precondicoes);

		saidasDesejaveis = new ArrayList<URI>();
		saidasDesejaveis.addAll(saidas);
		// Set<URI> set = new HashSet<URI>();
		// set.addAll(saidasDesejaveis);
		// // elimina saidas que sao usadas como entradas
		// set.retainAll(entradasDisponiveis);
		// for (int i = saidasDesejaveis.size()-1; saidasDesejaveis != null && i
		// >=0 ; i--) {
		// URI uri = saidasDesejaveis.get(i);
		// if (set.contains(uri)) {
		// set.remove(uri);
		// saidasDesejaveis.remove(i);
		// }
		// }

		saidasDescartadas = new ArrayList<URI>();
		saidasDescartadas.addAll(descartes);

		// efeitosDesejaveis = new ArrayList<URI>();
		// efeitosDesejaveis.addAll(efeitos);

		// processosPossiveis = new ArrayList<Objetivo>();

		processosDesejaveis = new ArrayList<Objetivo>();
		processosDesejaveis.addAll(objetivos);

		operacoesUteis = new ArrayList<Operacao>();

		operacoesUteisSePossiveis = new ArrayList<Operacao>();

		operacoesPossiveis = new ArrayList<Operacao>();

		// operacoesDescartadas = new ArrayList<Operacao>();

		caminhosDeExecucao = new ArrayList<List<Operacao>>();

		// grafoExecucao = new ArrayList<List<Operacao>>();

		seletor.selectOperacao();
	}

	// private boolean containsAllProcessosUsuario() {
	// boolean isTrue = true;
	//
	// Iterator iter1 = processosUsuario.iterator();
	// while (iter1 != null && iter1.hasNext()) {
	// boolean achou = false;
	// Objetivo objetivo1 = (Objetivo) iter1.next();
	//
	// Iterator iter2 = processosPossiveis.iterator();
	// while (iter2 != null && iter2.hasNext()) {
	// Objetivo objetivo2 = (Objetivo) iter2.next();
	// if (objetivo2.equals(objetivo1)) {
	// achou = true;
	// break;
	// }
	// }
	// isTrue &= achou;
	// }
	//
	// return isTrue;
	// }

	private void tornarOperacoesUteis() {
		Set<Operacao> diff = new HashSet<Operacao>();
		diff.addAll(operacoesUteisSePossiveis);
		diff.retainAll(operacoesPossiveis);

		Iterator iter1 = diff.iterator();
		while (iter1 != null && iter1.hasNext()) {
			Operacao operacao = (Operacao) iter1.next();

			if (!operacoesUteis.contains(operacao)) {
				operacoesUteis.add(operacao);

				Iterator iter2 = operacao.getSaidas().iterator();
				while (iter2 != null && iter2.hasNext()) {
					URI uri = (URI) iter2.next();

					if (!entradasDisponiveis.contains(uri))
						entradasDisponiveis.add(uri);
				}

				// iter2 = operacao.getEfeitos().iterator();
				// while (iter2 != null && iter2.hasNext()) {
				// URI uri = (URI) iter2.next();
				//
				// if (!precondicoesDisponiveis.contains(uri))
				// precondicoesDisponiveis.add(uri);
				// }
			}
		}
	}

	/**
	 * Seleciona as operacoes uteis para a composicao dos planos
	 * 
	 */
	private void selecionarOperacoesUteis() throws Exception {
		boolean aplicouRegra = true;
		boolean gerouPlano = false;

		// Set<Objetivo> oldProcessos = new HashSet<Objetivo>();
		Set<URI> oldEntradas = new HashSet<URI>();
		// Set<URI> oldPrecondicoes = new HashSet<URI>();
		Set<Operacao> oldOperacoes1 = new HashSet<Operacao>();
		Set<Operacao> oldOperacoes2 = new HashSet<Operacao>();
		Set<URI> oldSaidas = new HashSet<URI>();
		// Set<URI> oldEfeitos = new HashSet<URI>();

		// carrega primeiramente com as operacoes que atendem os objetivos
		{
			Set<Operacao> operacoes = seletor
					.getOperacaoPorObjetivo(processosUsuario);
			Iterator iter = operacoes.iterator();
			while (iter != null && iter.hasNext()) {
				Operacao operacao = (Operacao) iter.next();

				if (!operacoesUteisSePossiveis.contains(operacao)) {
					operacoesUteisSePossiveis.add(operacao);
					// Set<URI> diff = new HashSet<URI>();
					// diff.addAll(saidasDesejaveis);
					// diff.retainAll(operacao.getSaidas());
					// oldSaidas.addAll(diff);
				}
			}

			tornarOperacoesUteis();
		}

		while (aplicouRegra && !gerouPlano) {
			aplicouRegra = false;

			// Regra 3 - SaidasProcessosOuEfeitosDesejaveisEstaoConsumidos
			if (!oldSaidas.containsAll(saidasDesejaveis)
			/* || !oldProcessos.containsAll(processosDesejaveis) */
			/* || !oldEfeitos.containsAll(efeitosDesejaveis) */) {
				// Saidas
				// if (!oldSaidas.containsAll(saidasDesejaveis)) {
				Set<URI> diff = new HashSet<URI>();
				diff.addAll(saidasDesejaveis);
				diff.removeAll(oldSaidas);
				oldSaidas.addAll(saidasDesejaveis);

				// operacoes que produzem pelo menos uma das saidas desejaveis
				Iterator iter1 = diff.iterator();
				while (iter1 != null && iter1.hasNext()) {
					URI uri = (URI) iter1.next();
					Set<Operacao> operacoes = seletor.getOperacaoPorSaida(uri);

					Iterator iter2 = operacoes.iterator();
					while (iter2 != null && iter2.hasNext()) {
						Operacao operacao = (Operacao) iter2.next();

						if (!operacoesUteisSePossiveis.contains(operacao))
							operacoesUteisSePossiveis.add(operacao);
					}
				}
				// }

				// Efeitos
				// if (!oldEfeitos.containsAll(efeitosDesejaveis)) {
				// Set<URI> diff = new HashSet<URI>();
				// diff.addAll(efeitosDesejaveis);
				// diff.removeAll(oldEfeitos);
				// oldEfeitos.addAll(efeitosDesejaveis);
				//
				// // operacoes que produzem pelo menos uma dos efeitos
				// desejaveis
				// Iterator iter1 = diff.iterator();
				// while (iter1 != null && iter1.hasNext()) {
				// URI uri = (URI) iter1.next();
				// Set<Operacao> operacoes = seletor.getOperacaoPorEfeito(uri);
				//
				// Iterator iter2 = operacoes.iterator();
				// while (iter2 != null && iter2.hasNext()) {
				// Operacao operacao = (Operacao) iter2.next();
				//
				// if (!operacoesUteisSePossiveis.contains(operacao))
				// operacoesUteisSePossiveis.add(operacao);
				// }
				// }
				// }

				// Processos
				// if (!oldProcessos.containsAll(processosDesejaveis)) {
				// Set<Objetivo> diff = new HashSet<Objetivo>();
				// diff.addAll(processosDesejaveis);
				// diff.removeAll(oldProcessos);
				// oldProcessos.addAll(processosDesejaveis);
				//
				// // operacoes que implementam pelo menos um dos processos
				// desejaveis
				// Set<Operacao> operacoes =
				// seletor.getOperacaoPorAtividade(diff);
				//
				// Iterator iter = operacoes.iterator();
				// while (iter != null && iter.hasNext()) {
				// Operacao operacao = (Operacao) iter.next();
				//
				// if (!operacoesUteisSePossiveis.contains(operacao))
				// operacoesUteisSePossiveis.add(operacao);
				// }
				// }

				tornarOperacoesUteis();

				aplicouRegra = true;
				// Regra 4 - OperacoesUteisSePossiveisEstaoConsumidas
			} else if (!oldOperacoes1.containsAll(operacoesUteisSePossiveis)) {
				Set<Operacao> diff = new HashSet<Operacao>();
				diff.addAll(operacoesUteisSePossiveis);
				diff.removeAll(oldOperacoes1);
				oldOperacoes1.addAll(operacoesUteisSePossiveis);

				// torna entradas/precondicoes em saidas/efeitos desejaveis
				Iterator iter1 = diff.iterator();
				while (iter1 != null && iter1.hasNext()) {
					Operacao operacao = (Operacao) iter1.next();

					Iterator iter2 = operacao.getEntradas().iterator();
					while (iter2 != null && iter2.hasNext()) {
						URI uri = (URI) iter2.next();

						if (!saidasDesejaveis.contains(uri)
								&& !entradasDisponiveis.contains(uri))
							saidasDesejaveis.add(uri);
					}

					// iter2 = operacao.getPrecondicoes().iterator();
					// while (iter2 != null && iter2.hasNext()) {
					// URI uri = (URI) iter2.next();
					//
					// if (!efeitosDesejaveis.contains(uri) &&
					// !precondicoesDisponiveis.contains(uri))
					// efeitosDesejaveis.add(uri);
					// }
				}

				aplicouRegra = true;
				// Regra 2 - OperacoesPossiveisEstaoConsumidasOuPlanoPossivel
			} else if (!(oldOperacoes2.containsAll(operacoesPossiveis) || gerouPlano)) {
				Set<Operacao> diff = new HashSet<Operacao>();
				diff.addAll(operacoesPossiveis);
				diff.removeAll(oldOperacoes2);
				oldOperacoes2.addAll(operacoesPossiveis);

				// torna saidas/processos em entradas/processos possiveis
				Iterator iter1 = diff.iterator();
				while (iter1 != null && iter1.hasNext()) {
					Operacao operacao = (Operacao) iter1.next();

					// if (!processosPossiveis.contains(operacao.getObjetivo()))
					// processosPossiveis.add(operacao.getObjetivo());

					Iterator iter2 = operacao.getSaidas().iterator();
					while (iter2 != null && iter2.hasNext()) {
						URI uri = (URI) iter2.next();

						if (!entradasPossiveis.contains(uri))
							entradasPossiveis.add(uri);
					}

					// iter2 = operacao.getEfeitos().iterator();
					// while (iter2 != null && iter2.hasNext()) {
					// URI uri = (URI) iter2.next();
					//
					// if (!precondicoesPossiveis.contains(uri))
					// precondicoesPossiveis.add(uri);
					// }
				}

				aplicouRegra = true;
				// Regra 1 - EntradasPreCondicoesPossiveisEstaoConsumidas
			} else if (!oldEntradas.containsAll(entradasPossiveis)
			/* || !oldPrecondicoes.containsAll(precondicoesPossiveis) */) {
				// Entradas
				if (!oldEntradas.containsAll(entradasPossiveis)) {
					Set<URI> diff = new HashSet<URI>();
					diff.addAll(entradasPossiveis);
					diff.removeAll(oldEntradas);
					oldEntradas.addAll(entradasPossiveis);

					// operacoes que necessitam apenas das entradas possiveis
					Iterator iter1 = diff.iterator();
					while (iter1 != null && iter1.hasNext()) {
						URI uri = (URI) iter1.next();
						Set<Operacao> operacoes = seletor
								.getOperacaoPorEntrada(uri);

						Iterator iter2 = operacoes.iterator();
						while (iter2 != null && iter2.hasNext()) {
							Operacao operacao = (Operacao) iter2.next();

							if (!operacoesPossiveis.contains(operacao)) {
								if (entradasPossiveis.containsAll(operacao
										.getEntradas()))
									operacoesPossiveis.add(operacao);
							}
						}
					}
				}

				// Precondicoes
				// if (!oldPrecondicoes.containsAll(precondicoesPossiveis)) {
				// Set<URI> diff = new HashSet<URI>();
				// diff.addAll(precondicoesPossiveis);
				// diff.removeAll(oldPrecondicoes);
				// oldPrecondicoes.addAll(precondicoesPossiveis);
				//
				// //operacoes que necessitam apenas das precondicoes possiveis
				// Iterator iter1 = diff.iterator();
				// while (iter1 != null && iter1.hasNext()) {
				// URI uri = (URI) iter1.next();
				// Set<Operacao> operacoes =
				// seletor.getOperacaoPorPrecondicao(uri);
				//
				// Iterator iter2 = operacoes.iterator();
				// while (iter2 != null && iter2.hasNext()) {
				// Operacao operacao = (Operacao) iter2.next();
				//
				// if (!operacoesPossiveis.contains(operacao)) {
				// if
				// (precondicoesPossiveis.containsAll(operacao.getPrecondicoes()))
				// operacoesPossiveis.add(operacao);
				// }
				// }
				// }
				// }

				tornarOperacoesUteis();

				aplicouRegra = true;
				// Regra 5 - SaidasEfeitosProcessosPossiveis
			} else if (entradasPossiveis.containsAll(saidasUsuario)
			// && precondicoesPossiveis.containsAll(efeitosUsuario)
			/* && containsAllProcessosUsuario() */) {
				gerouPlano = true;
			}
		}

		if (!gerouPlano) {
			throw new Exception("N�o foi poss�vel encontrar uma composi��o");
		}

		/*
		 * AQUIIII System.out.println("operacoesUteis = " + operacoesUteis);
		 */

		// para cada operacao em operacoesUteis fa�a
		// se operacao produz alguma saidaDescartada entao
		// remover operacao de operacoesUteis
		// adicionar operacao em operacoesDescartadas;
		// fim-para
		// for (int i=0; i < operacoesUteis.size(); i++) {
		// Operacao operacao = (Operacao) operacoesUteis.get(i);
		// Set<URI> saidas = new HashSet<URI>(operacao.getSaidas());
		// for (int j=0; j < saidasDescartadas.size(); j++) {
		// if (saidas.contains(saidasDescartadas.get(j))) {
		// if (!operacoesDescartadas.contains(operacao))
		// operacoesDescartadas.add(operacao);
		// break;
		// }
		// }
		// }
		// operacoesUteis.removeAll(operacoesDescartadas);
		//
		// System.out.println("operacoesDescartadas = " + operacoesDescartadas);
	}

	/**
	 * Verificacao da completude de um caminho possivel
	 * 
	 */
	private boolean isCaminhoCompleto(List<Operacao> caminho) {
		// List<URI> entradas1 = new ArrayList<URI>();
		// entradas1.addAll(entradasUsuario);
		//
		// List<URI> saidas1 = new ArrayList<URI>();
		// saidas1.addAll(saidasUsuario);
		//
		// List<URI> entradas2 = new ArrayList<URI>();
		//
		// List<URI> saidas2 = new ArrayList<URI>();
		//
		// Iterator iter = caminho.iterator();
		// while (iter.hasNext()) {
		// Operacao operacao = (Operacao) iter.next();
		// entradas2.addAll(operacao.getEntradas());
		// saidas2.addAll(operacao.getSaidas());
		// }
		//
		// if (entradas2.containsAll(entradas1)) {
		// if (saidas1.isEmpty()) {
		// entradas2.removeAll(saidas2);
		// entradas2.removeAll(entradas1);
		//
		// return entradas2.isEmpty();
		// } else if (saidas2.containsAll(saidas1)) {
		// for (int i=0; i < saidas1.size(); i++) {
		// URI uri = saidas1.get(i);
		// saidas2.remove(uri);
		// }
		//
		// entradas2.removeAll(saidas2);
		// entradas2.removeAll(entradas1);
		//
		// return entradas2.isEmpty();
		// } else {
		// return false;
		// }
		// } else {
		// return false;
		// }

		boolean containsPrecondicoes = true;
		boolean containsEfeitos = true;

		List<URI> precondicoes = new ArrayList<URI>();
		List<URI> efeitos = new ArrayList<URI>();

		Iterator iter = caminho.iterator();
		while (iter.hasNext()) {
			Operacao operacao = (Operacao) iter.next();
			precondicoes.addAll(operacao.getPrecondicoes());
			efeitos.addAll(operacao.getEfeitos());
		}

		if (precondicoesUsuario.size() > 0)
			containsPrecondicoes = precondicoes
					.containsAll(precondicoesUsuario);

		if (efeitosUsuario.size() > 0)
			containsEfeitos = efeitos.containsAll(efeitosUsuario);

		return containsPrecondicoes && containsEfeitos;
	}

	/**
	 * Criacao de caminhos de execucao possiveis
	 * 
	 */
	private List<List<Operacao>> gerarCaminhosPossiveis(Object vetor[][],
			List<Operacao> caminho, boolean flag) {
		List<List<Operacao>> caminhos = new ArrayList<List<Operacao>>();
		caminhos.add(caminho);

		for (int i = 0; i < vetor.length; i++) {
			List<List<Operacao>> temp = caminhos;
			caminhos = new ArrayList<List<Operacao>>();

			Iterator<List<Operacao>> iter1 = temp.iterator();
			while (iter1.hasNext()) {
				List<Operacao> oldCaminho = iter1.next();
				Set<String> servicos = new HashSet<String>();
				Set<Objetivo> objetivos1 = new HashSet<Objetivo>();

				// servicos que compoe o caminho
				Iterator iter2 = oldCaminho.iterator();
				while (iter2 != null && iter2.hasNext()) {
					Operacao operacao = (Operacao) iter2.next();
					servicos.add(operacao.getServico());
					objetivos1.add(operacao.getObjetivo());
				}

				// acrescenta uma nova operacao ao caminho
				for (int j = 0; vetor[i] != null && j < vetor[i].length; j++) {
					List<Operacao> newCaminho = new ArrayList<Operacao>();
					newCaminho.addAll(oldCaminho);
					Operacao operacao = (Operacao) vetor[i][j];

					// remove operacoes repetidas
					if (!newCaminho.contains(operacao)) {
						// impedir composicao esdruxula
						// Situacao 1 - a primeira operacao do caminho
						if (oldCaminho.isEmpty())
							newCaminho.add((Operacao) vetor[i][j]);
						else
						// Situacao 2 - o mesmo servico
						if (servicos.contains(operacao.getServico()))
							newCaminho.add((Operacao) vetor[i][j]);
						else
						// Situacao 3 - nenhum servico do caminho implementa o
						// objetivo da operacao E
						// o servico da operacao nao implementa os objetivos de
						// um dos servicos do caminho
						if (!containsObjetivo(servicos.toArray(new String[0]),
								operacao.getObjetivo())
								&& !containsObjetivo(operacao.getServico(),
										servicos.toArray(new String[0]))) {
							newCaminho.add((Operacao) vetor[i][j]);
						}
					} else {
						caminhos.add(newCaminho);
					}
					// um novo caminho foi gerado
					if (oldCaminho.size() != newCaminho.size())
						caminhos.add(newCaminho);
				}
			}
		}

		return caminhos;
	}

	// private Set<Operacao> obterOperacaoPorProcesso(List<Operacao> operacoes,
	// Objetivo objetivo) {
	// Set<Operacao> set = new HashSet<Operacao>();
	//
	// Iterator iter = operacoes.iterator();
	// while (iter != null && iter.hasNext()) {
	// Operacao operacao = (Operacao) iter.next();
	//
	// if (operacao.getObjetivo().equals(objetivo))
	// set.add(operacao);
	// }
	//
	// return set;
	// }

	// private Set<Operacao> obterOperacaoPorEntrada(List<Operacao> operacoes,
	// URI uri) {
	// Set<Operacao> set = new HashSet<Operacao>();
	//
	// Iterator iter = operacoes.iterator();
	// while (iter != null && iter.hasNext()) {
	// Operacao operacao = (Operacao) iter.next();
	//
	// if (operacao.consomeEntrada(uri))
	// set.add(operacao);
	// }
	//
	// return set;
	// }

	// private Set<Operacao> obterOperacaoPorSaida(List<Operacao> operacoes, URI
	// uri) {
	// Set<Operacao> set = new HashSet<Operacao>();
	//
	// Iterator iter = operacoes.iterator();
	// while (iter != null && iter.hasNext()) {
	// Operacao operacao = (Operacao) iter.next();
	//
	// if (operacao.produzSaida(uri))
	// set.add(operacao);
	// }
	//
	// return set;
	// }

	// private Set<Operacao> obterOperacaoPorEfeito(List<Operacao> operacoes,
	// URI uri) {
	// Set<Operacao> set = new HashSet<Operacao>();
	//
	// Iterator iter = operacoes.iterator();
	// while (iter != null && iter.hasNext()) {
	// Operacao operacao = (Operacao) iter.next();
	//
	// if (operacao.produzEfeito(uri))
	// set.add(operacao);
	// }
	//
	// return set;
	// }

	private boolean containsCaminhoDeExecucao(List<Operacao> caminho) {
		Iterator<List<Operacao>> iter = caminhosDeExecucao.iterator();
		while (iter.hasNext()) {
			List<Operacao> outro = iter.next();

			if (outro.containsAll(caminho) && caminho.containsAll(outro))
				return true;
		}

		return false;
	}

	/**
	 * Criacao de caminhos execucao a partir das operacoes uteis
	 * 
	 */
	private void gerarCaminhosDeExecucao() throws Exception {
		// cria vetor com operacoes uteis que produzem saidas e processos do
		// usuario
		int i = 0;
		Iterator iter1 = null;
		Object vetor[][] = new Object[saidasUsuario.size() /*
															 * +
															 * efeitosUsuario.size
															 * ()
															 */
				+ processosUsuario.size()][];
		List<URI> index = new ArrayList<URI>();
		/*
		 * AQUIIIII System.out.println("Operacoes por Saida");
		 */
		iter1 = saidasUsuario.iterator();
		while (iter1.hasNext()) {
			URI uri = (URI) iter1.next();
			Set<Operacao> operacoes = seletor.getOperacaoPorSaida(
					operacoesUteis.toArray(new Operacao[0]), uri);
			if (!index.contains(uri)) {
				/*
				 * AQUIIIII
				 * 
				 * System.out.println("" + uri + "=" + operacoes);
				 */
				index.add(uri);
				vetor[i++] = operacoes.toArray();
			}
		}

		// iter1 = efeitosUsuario.iterator();
		// while (iter1.hasNext()) {
		// URI uri = (URI) iter1.next();
		// Set<Operacao> operacoes = obterOperacaoPorEfeito(operacoesUteis,
		// uri);
		// if (!index.contains(uri)) {
		// index.add(uri);
		// vetor[i++] = operacoes.toArray();
		// }
		// }

		// System.out.println("Operacoes por Objetivo");
		iter1 = processosUsuario.iterator();
		while (iter1.hasNext()) {
			Objetivo objetivo = (Objetivo) iter1.next();
			Set<Operacao> operacoes = seletor.getOperacaoPorObjetivo(
					operacoesUteis.toArray(new Operacao[0]), objetivo);
			URI uri = objetivo.getURI();
			if (!index.contains(uri)) {
				/*
				 * AQUIIIII System.out.println("" + uri + "=" + operacoes);
				 */
				index.add(uri);
				vetor[i++] = operacoes.toArray();
			}
		}

		// gera caminhos de execucao possiveis
		List<List<Operacao>> caminhosPossiveis = gerarCaminhosPossiveis(vetor,
				new ArrayList<Operacao>(), true);
		log.debug("Quantidade de caminhos gerados: " + caminhosPossiveis.size());
		Iterator<List<Operacao>> iter2 = caminhosPossiveis.iterator();
		int aux = 0;
		while (iter2.hasNext()) {
			List<Operacao> caminho = iter2.next();
			log.debug("Caminho " + ++aux + "\t" + caminho);
			List<List<Operacao>> novosCaminhos = melhorarCaminho(
					entradasDesejaveis, null /* precondicoesUsuario */, index,
					caminho);
			// System.out.println("novosCaminhos = " + caminhosPossiveis);

			Iterator<List<Operacao>> iter3 = novosCaminhos.iterator();
			while (iter3.hasNext()) {
				caminho = iter3.next();

				caminho = removerOperacaoRedundante(caminho);

				if (isCaminhoCompleto(caminho)) {
					if (!containsCaminhoDeExecucao(caminho)) {
						caminho = ordenarCaminho(caminho);
						if (caminho != null)
							caminhosDeExecucao.add(caminho);
					}
				}
			}
		}

		// // verifica se cada caminho eh completo
		// List<List<Operacao>> caminhosIncompletos = new
		// ArrayList<List<Operacao>>();
		// Iterator<List<Operacao>> iter1 = caminhosPossiveis.iterator();
		// while (iter1.hasNext()) {
		// List<Operacao> caminho = iter1.next();
		// // adiciona em caminhoExecucao
		// if (isCaminhoCompleto(caminho)) {
		// caminho = removerOperacaoRedundante(caminho);
		//
		// if (!containsCaminho(caminho)) {
		// caminho = ordenarCaminho(caminho);
		// caminhosDeExecucao.add(caminho);
		// }
		// } else {
		// caminhosIncompletos.add(caminho);
		// }
		// }
		//
		// // gera caminhos de execucao possiveis (2a tentativa)
		// if (caminhosIncompletos.size() > 0) {
		// // cria vetor com operacoes uteis que necessitam das entradas do
		// usuario
		// i = 0;
		// vetor = new Object[entradasUsuario.size()][];
		//
		// iter = entradasUsuario.iterator();
		// while (iter.hasNext()) {
		// Set<Operacao> operacoes = obterOperacaoPorEntrada(operacoesUteis,
		// (URI) iter.next());
		// vetor[i++] = operacoes.toArray();
		// }
		//
		// // refaz caminho possivel com operacoes uteis que necessitam das
		// entradas do usuario
		// iter1 = caminhosIncompletos.iterator();
		// while (iter1.hasNext()) {
		// List<Operacao> item = iter1.next();
		// caminhosPossiveis = gerarCaminhosPossiveis(vetor, item);
		//
		// // verifica se cada caminho eh completo
		// Iterator<List<Operacao>> iter2 = caminhosPossiveis.iterator();
		// while (iter2.hasNext()) {
		// List<Operacao> caminho = iter2.next();
		// // adiciona em caminhoExecucao
		// if (isCaminhoCompleto(caminho)) {
		// caminho = removerOperacaoRedundante(caminho);
		//
		// if (!containsCaminho(caminho)) {
		// caminho = ordenarCaminho(caminho);
		// caminhosDeExecucao.add(caminho);
		// }
		// }
		// }
		// }
		// }

		/*
		 * AQUIIIII System.out.println("caminhosDeExecucao = " +
		 * caminhosDeExecucao);
		 */
	}

	private boolean containsObjetivo(String[] servicos, Objetivo objetivo) {
		boolean isTrue = false;

		for (int i = 0; servicos != null && i < servicos.length; i++) {
			Set<Objetivo> objetivos = seletor
					.getObjetivoPorServico(new String[] { servicos[i] });
			isTrue = containsObjetivo(objetivos.toArray(new Objetivo[0]),
					objetivo);

			if (isTrue)
				break;
		}

		return isTrue;
	}

	private boolean containsObjetivo(String servico, String[] servicos) {
		boolean isTrue = false;
		Set<Objetivo> objetivos = seletor
				.getObjetivoPorServico(new String[] { servico });
		Objetivo[] outros = objetivos.toArray(new Objetivo[0]);
		objetivos = seletor.getObjetivoPorServico(servicos);
		Objetivo[] um = objetivos.toArray(new Objetivo[0]);

		for (int i = 0; um != null && i < um.length; i++) {
			isTrue = containsObjetivo(outros, um[i]);

			if (isTrue)
				break;
		}

		return isTrue;
	}

	private boolean containsObjetivo(Objetivo[] set, Objetivo objetivo2) {
		boolean isTrue = false;

		for (int i = 0; set != null && i < set.length; i++) {
			Objetivo objetivo1 = set[i];

			if (objetivo2.equals(objetivo1)) {
				isTrue = true;
				break;
			}
		}

		return isTrue;
	}

	private List<List<Operacao>> melhorarCaminho(List<URI> entradas,
			List<URI> precondicoes, List<URI> index, List<Operacao> caminho)
			throws Exception {
		List<List<Operacao>> caminhos = new ArrayList<List<Operacao>>();

		List<URI> entradasDisponiveis = new ArrayList<URI>();
		entradasDisponiveis.addAll(entradas);

		// List<URI> precondicoesDisponiveis = new ArrayList<URI>();
		// precondicoesDisponiveis.addAll(precondicoes);

		Set<URI> entradasNaoCombinadas = new HashSet<URI>();

		// Set<URI> precondicoesNaoCombinadas = new HashSet<URI>();

		List<URI> itensJaCombinados = new ArrayList<URI>();
		itensJaCombinados.addAll(index);

		// Set<String> servicosDisponiveis = new HashSet<String>();

		for (int i = 0; i < caminho.size(); i++) {
			Operacao operacao = caminho.get(i);
			// servicosDisponiveis.add(operacao.getServico());
			entradasNaoCombinadas.addAll(operacao.getEntradas());
			entradasNaoCombinadas.removeAll(entradasDisponiveis);
			entradasNaoCombinadas.removeAll(itensJaCombinados);

			// if (precondicoesDisponiveis.size() > 0) {
			// precondicoesNaoCombinadas.addAll(operacao.getPrecondicoes());
			// precondicoesNaoCombinadas.removeAll(precondicoesDisponiveis);
			// precondicoesNaoCombinadas.removeAll(itensJaCombinados);
			// }
		}

		if (entradasNaoCombinadas.size() > 0 /*
											 * ||
											 * precondicoesNaoCombinadas.size()
											 * > 0
											 */) {
			int j = 0;
			Object[][] vetor = new Object[entradasNaoCombinadas.size() /*
																		 * +
																		 * precondicoesNaoCombinadas
																		 * .
																		 * size(
																		 * )
																		 */][];

			Iterator iter1 = entradasNaoCombinadas.iterator();
			while (iter1.hasNext()) {
				URI uri = (URI) iter1.next();
				if (saidasDescartadas.contains(uri))
					throw new Exception(
							"N�o foi poss�vel encontrar uma composi��o");
				Set<Operacao> operacoes = seletor.getOperacaoPorSaida(
						operacoesUteis.toArray(new Operacao[0]), uri);
				// remove a duplicidade
				operacoes.removeAll(caminho);
				// // remover composicoes esdruxulas
				// Set<Operacao> diff = new HashSet<Operacao>();
				// Iterator iter2 = operacoes.iterator();
				// while (iter2 != null && iter2.hasNext()){
				// Operacao operacao = (Operacao) iter2.next();
				// if (!servicosDisponiveis.contains(operacao.getServico())) {
				// Set<Objetivo> objetivos =
				// seletor.getObjetivoPorServico(servicosDisponiveis.toArray(new
				// String[0]));
				// if (containsObjetivo(objetivos, operacao.getObjetivo()))
				// diff.add(operacao);
				// }
				// }
				// operacoes.removeAll(diff);

				if (operacoes.size() > 0) {
					vetor[j++] = operacoes.toArray();
					entradasDisponiveis.add(uri);
					itensJaCombinados.add(uri);
				}
			}

			// iter1 = precondicoesNaoCombinadas.iterator();
			// while (iter1.hasNext()) {
			// URI uri = (URI) iter1.next();
			// Set<Operacao> operacoes = obterOperacaoPorEfeito(operacoesUteis,
			// uri);
			// operacoes.removeAll(caminho);
			// if (operacoes.size() > 0) {
			// vetor[j++] = operacoes.toArray();
			// precondicoesDisponiveis.add(uri);
			// itensJaCombinados.add(uri);
			// }
			// }

			List<List<Operacao>> caminhosPossiveis = gerarCaminhosPossiveis(
					vetor, caminho, false);

			Iterator<List<Operacao>> iter2 = caminhosPossiveis.iterator();
			while (iter2.hasNext()) {
				List<Operacao> newCaminho = iter2.next();
				caminhos.addAll(melhorarCaminho(entradasDisponiveis,
						null /* precondicoesDisponiveis */, itensJaCombinados,
						newCaminho));
			}
		} else {
			caminhos.add(caminho);
		}

		return caminhos;
	}

	/**
	 * Verifica se uma operacao pertence a outro caminho
	 * 
	 */
	private boolean pertencerAOutroCaminho(Operacao operacao,
			List<Operacao> atual) {
		Iterator<List<Operacao>> iter = caminhosDeExecucao.iterator();
		while (iter.hasNext()) {
			List<Operacao> caminho = iter.next();

			if (!caminho.equals(atual) && caminho.contains(operacao))
				return true;
		}

		return false;
	}

	/**
	 * Remove operacoes redundantes de um caminho
	 * 
	 */
	private List<Operacao> removerOperacaoRedundante(List<Operacao> caminho)
			throws Exception {
		Map<Operacao, Set<Operacao>> grafo1 = new HashMap<Operacao, Set<Operacao>>();
		Map<Operacao, Set<Operacao>> grafo2 = new HashMap<Operacao, Set<Operacao>>();
		List<Operacao> oldCaminho = new ArrayList<Operacao>();
		List<Operacao> tempCaminho = new ArrayList<Operacao>();
		List<Operacao> newCaminho = new ArrayList<Operacao>();
		newCaminho.addAll(caminho);

		Iterator iter1 = caminho.iterator();
		while (iter1.hasNext()) {
			Operacao operacao = (Operacao) iter1.next();

			Set<URI> entradas = new HashSet<URI>();
			entradas.addAll(operacao.getEntradas());

			Set<URI> saidas = new HashSet<URI>();
			saidas.addAll(operacao.getSaidas());

			Iterator iter2 = entradas.iterator();
			while (iter2.hasNext()) {
				Set<Operacao> operacoes = seletor.getOperacaoPorSaida(
						caminho.toArray(new Operacao[0]), (URI) iter2.next());
				// remove a operacao que produz uma saida que serve como entrada
				// pela si mesma
				operacoes.remove(operacao);
				grafo1.put(operacao, operacoes);
			}

			iter2 = saidas.iterator();
			while (iter2.hasNext()) {
				Set<Operacao> operacoes = seletor.getOperacaoPorEntrada(
						caminho.toArray(new Operacao[0]), (URI) iter2.next());
				// remove a operacao que produz uma saida que serve como entrada
				// pela si mesma
				operacoes.remove(operacao);
				grafo2.put(operacao, operacoes);
			}
		}

		iter1 = caminho.iterator();
		while (iter1.hasNext()) {
			Operacao operacao = (Operacao) iter1.next();
			Operacao[] transicao1 = grafo1.get(operacao).toArray(
					new Operacao[0]);
			Operacao[] transicao2 = grafo2.get(operacao).toArray(
					new Operacao[0]);

			// mais de uma operacao produz a mesma saida
			// verificar se elas tem as mesmas entradas
			if (transicao1.length > 1) {
				for (int i = 0; i < transicao1.length - 1; i++) {
					List<URI> op1 = transicao1[i].getEntradas();

					for (int j = i + 1; j < transicao1.length; j++) {
						List<URI> op2 = transicao1[j].getEntradas();

						if (op1.containsAll(op2) && op2.containsAll(op1)) {
							if (pertencerAOutroCaminho(transicao1[i], caminho)) {
								oldCaminho.add(transicao1[i]);
							} else if (pertencerAOutroCaminho(transicao1[j],
									caminho)) {
								oldCaminho.add(transicao1[j]);
							}
						}
					}
				}
			}

			// mais de uma operacao consome a mesma entrada
			// verificar se elas tem as mesmas saidas
			if (transicao2.length > 1) {
				for (int i = 0; i < transicao2.length - 1; i++) {
					List<URI> op1 = transicao2[i].getSaidas();

					for (int j = i + 1; j < transicao2.length; j++) {
						List<URI> op2 = transicao2[j].getSaidas();

						if (op1.containsAll(op2) && op2.containsAll(op1)) {
							if (pertencerAOutroCaminho(transicao2[i], caminho)) {
								oldCaminho.add(transicao2[i]);
							} else if (pertencerAOutroCaminho(transicao2[j],
									caminho)) {
								oldCaminho.add(transicao2[j]);
							}
						}
					}
				}
			}

			if (transicao1.length == 0 && transicao2.length == 0) {
				tempCaminho.add(operacao);
			}
		}

		// caminho contendo uma unica operacao
		if (tempCaminho.size() > 1) {
			Operacao[] operacoes = tempCaminho.toArray(new Operacao[0]);

			for (int i = 0; i < operacoes.length - 1; i++) {
				List<URI> op1 = operacoes[i].getEntradas();

				for (int j = i + 1; j < operacoes.length; j++) {
					List<URI> op2 = operacoes[j].getEntradas();

					if (op1.containsAll(op2) && op2.containsAll(op1)) {
						if (pertencerAOutroCaminho(operacoes[i], caminho)) {
							oldCaminho.add(operacoes[i]);
						} else if (pertencerAOutroCaminho(operacoes[j], caminho)) {
							oldCaminho.add(operacoes[j]);
						}
					}
				}
			}
		}

		newCaminho.removeAll(oldCaminho);

		/*
		 * AQUIIIII System.out.println("caminhoNaoRedundante = " + newCaminho);
		 */

		return newCaminho;
	}

	/**
	 * Ordena operacoes de um caminho
	 * 
	 */
	private List<Operacao> ordenarCaminho(List<Operacao> caminho)
			throws Exception {
		List<Operacao> oldCaminho = new ArrayList<Operacao>();
		oldCaminho.addAll(caminho);

		List<Operacao> newCaminho = new ArrayList<Operacao>();

		List<URI> entradas1 = new ArrayList<URI>();
		// entradas1.addAll(entradasUsuario);

		for (int i = 0; i < processosUsuario.size(); i++) {
			Objetivo objetivo = processosUsuario.get(i);
			// List<URI> entradas1 = new ArrayList<URI>();

			List list = objetivo.getEntradas();
			for (int j = 0; list != null && j < list.size(); j++) {
				Conceito conceito = (Conceito) list.get(j);
				URI uri = URI.create(conceito.getURI());
				if (!entradas1.contains(uri))
					entradas1.add(uri);
			}

			while (true) {
				boolean achou = false;

				for (int j = 0; j < oldCaminho.size(); j++) {
					Operacao operacao = oldCaminho.get(j);

					List<URI> entradas2 = operacao.getEntradas();

					if (entradas1.containsAll(entradas2)) {
						newCaminho.add(operacao);

						List<URI> saidas = operacao.getSaidas();

						for (int k = 0; k < saidas.size(); k++) {
							URI uri = saidas.get(k);
							if (!entradas1.contains(uri))
								entradas1.add(uri);
						}

						achou = true;
						break;
					}
				}

				if (!achou)
					break;

				oldCaminho.removeAll(newCaminho);
			}
		}

		if (oldCaminho.size() != 0) {
			log.info("N�o foi poss�vel ordenar o caminho = " + caminho);
			log.info("caminhoOrdenado = " + newCaminho);
			return null;
		}

		// while (true) {
		// boolean achou = false;
		//
		// for (int i=0; i < oldCaminho.size(); i++) {
		// Operacao operacao = oldCaminho.get(i);
		//
		// List<URI> entradas2 = operacao.getEntradas();
		//
		// if (entradas1.containsAll(entradas2)) {
		// newCaminho.add(operacao);
		//
		// List<URI> saidas = operacao.getSaidas();
		//
		// for (int j=0; j < saidas.size(); j++) {
		// URI uri = saidas.get(j);
		// if (!entradas1.contains(uri))
		// entradas1.add(uri);
		// }
		//
		// achou = true;
		// break;
		// }
		// }
		//
		// if (!achou) {
		// // throw new Exception("N�o foi poss�vel ordenar o caminho.");
		// System.out.println("N�o foi poss�vel ordenar o caminho = " +
		// caminho);
		// return null;
		// }
		//
		// oldCaminho.removeAll(newCaminho);
		//
		// if (oldCaminho.size() == 0) break;
		// }

		/*
		 * AQUIIIII System.out.println("caminhoOrdenado = " + newCaminho);
		 */

		return newCaminho;
	}

	/**
	 * Criacao do grafo de execucao a partir dos caminhos de execucao
	 * 
	 */
	// private void criarGrafoExecucao() throws Exception {
	// Iterator<List<Operacao>> iter = caminhosExecucao.iterator();
	// while (iter.hasNext()) {
	// List<Operacao> caminho = iter.next();
	// // remove operacoes redundantes do caminho
	// caminho = removerOperacaoRedundante(caminho);
	// // reordena operacoes do caminho
	// // caminho = reordenarCaminho(caminho);
	// if (caminho.size() > 0 && !grafoExecucao.contains(caminho)) {
	// grafoExecucao.add(caminho);
	// }
	// }

	// System.out.println("grafoExecucao = " + grafoExecucao);
	// }

	/**
	 * Otimizacao do grafo de execucao ordenando pelo menor caminho
	 * 
	 */
	// private void otimizarGrafoExecucao() {
	// int menor = 0;
	// int tamanho = grafoExecucao.size() > 0 ? grafoExecucao.get(menor).size()
	// : 0;
	//
	// for (int i=1; i < grafoExecucao.size(); i++) {
	// if (tamanho > grafoExecucao.get(i).size()) {
	// List<Operacao> troca = grafoExecucao.get(menor);
	// grafoExecucao.set(menor, grafoExecucao.get(i));
	// grafoExecucao.set(i, troca);
	// menor = i;
	// }
	// }
	//
	// System.out.println("grafoOtimizado = " + grafoExecucao);
	// }

	// public static void main(String[] args) {
	// CompositorSemantico compositor = new CompositorSemantico();
	//
	// compositor.entradaUsuario = new HashSet<URI>();
	// compositor.entradaUsuario.add(URI.create("http://www.w3.org/2001/XMLSchema#string"));
	// compositor.entradaUsuario.add(URI.create("http://www.daml.ecs.soton.ac.uk/ont/currency.owl#Currency"));
	//
	// compositor.saidaUsuario = new HashSet<URI>();
	// compositor.saidaUsuario.add(URI.create("http://www.mindswap.org/2004/owl-s/concepts.owl#Price"));
	//
	// compositor.atividadeUsuario = new HashSet<URI>();
	// compositor.atividadeUsuario.add(URI.create("http://www.mindswap.org/2004/owl-s/1.1/BookFinder.owl#BookFinderProcess"));
	// compositor.atividadeUsuario.add(URI.create("http://www.mindswap.org/2004/owl-s/1.1/AmazonBookPrice.owl#AmazonPriceProcess"));
	// //
	// compositor.atividadeUsuario.add(URI.create("http://www.mindswap.org/2004/owl-s/1.1/BNPrice.owl#BNPriceProcess"));
	// compositor.atividadeUsuario.add(URI.create("http://www.mindswap.org/2004/owl-s/1.1/CurrencyConverter.owl#CurrencyConverterProcess"));
	//
	// compositor.doCompor();
	// }

}
